package own.stu.jobgib.playown.alg.leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

public class LengthOfLongestSubstringKDistinct {

    public static void main(String[] args) {
        //System.out.println(lengthOfLongestSubstringKDistinct("eqgkcwGFvjjmxutystqdfhuMblWbylgjxsxgnoh", 16));
        System.out.println(lengthOfLongestSubstringKDistinct_ii("eqgkcwGFvjjmxutystqdfhuMblWbylgjxsxgnoh", 16));
        System.out.println(" ======================== ");
        System.out.println(lengthOfLongestSubstringKDistinct_iii("eqgkcwGFvjjmxutystqdfhuMblWbylgjxsxgnoh", 16));
    }

    public static int lengthOfLongestSubstringKDistinct_iii(String s, int k) {
        // write your code here
        if(s == null || s.length() == 0 || k <= 0){
            return 0;
        }

        if(s.length() <= k){
            return s.length();
        }

        int ans = 0;
        int n = s.length();
        Map<Character, Integer> map = new HashMap<>();
        int cnt = 0;
        char c = ' ';
        for(int i = 0, j = 0; i < n; i ++){
            while(j < n && cnt <= k){
                c = s.charAt(j);
                if(map.containsKey(c)){
                    map.put(c, map.get(c) + 1);
                }else{
                    if(cnt == k){
                        break;
                    }
                    cnt += 1;
                    map.put(c, 1);
                }
                j += 1;
            }
            c = s.charAt(i);
            ans = Math.max(ans, j - i);
            System.out.println("i = " + i + ", j = " + j + ", cnt = " + cnt + ", " + map);
            if (map.get(c) == 1){
                cnt -= 1;
            }
            map.put(c, map.get(c) - 1);
        }

        return ans;
    }

    public static int lengthOfLongestSubstringKDistinct_ii(String s, int k) {
        // write your code here
        // int[] map = new int[Character.MAX_VALUE];
        Map<Character, Integer> map = new HashMap<>();
        int dit = 0;
        int len = 0;
        char c = ' ';
        for (int i = 0, j = 0; i < s.length(); i++){
            while (j < s.length() && dit <= k){
                c = s.charAt(j);
                map.put(c, map.getOrDefault(c, 0) + 1);

                if (map.get(c) == 1){
                    if (dit == k){
                        map.put(c, map.get(c) - 1);
                        break;
                    }
                    dit++;
                }
                j++;
            }

            c = s.charAt(i);
            len = Math.max(len, j - i);

            System.out.println("i = " + i + ", j = " + j + ", cnt = " + dit + ", " + map);
            if (map.get(c) == 1){
                dit--;
            }
            map.put(c, map.get(c) - 1);
        }
        return len;
    }

    public static int lengthOfLongestSubstringKDistinct(String s, int k) {
        // write your code here
        int[] map = new int[Character.MAX_VALUE];
        int dit = 0;
        int len = 0;
        for (int i = 0, j = 0; i < s.length(); i++){
            while (j < s.length() && dit <= k){
                map[s.charAt(j)]++;
                if (map[s.charAt(j)] == 1){
                    if (dit == k){
                        map[s.charAt(j)]--;
                        break;
                    }
                    dit++;
                }
                j++;
            }
            len = Math.max(len, j - i);
            if (map[s.charAt(i)] == 1){
                dit--;
            }
            map[s.charAt(i)]--;
        }
        return len;
    }
}
